package com.lzy.tricbuild4_ac_hash;

import java.util.*;

/**
 * @ClassName:   AcHashTric
 * @Author:      Li ZhenYong
 * @description:  AC自动机字典树，使用散列表保存子节点
 * @Date:        2022-04-05 22:46
 * @Version:  1.0
 */
public class AcHashTric {

	private AcHashNode root = new AcHashNode("/"); // 存储无意义字符

	/**
	 * 往Tric树中插入一个字符串数据
	 * @param text
	 */
	public void insert(String text) {
		if(text == null || text.trim().length() == 0) return;

		AcHashNode p = root;

		// 进行遍历插入字符串到字典树中
		for (int i = 0; i < text.length(); i++) {
			String s = text.charAt(i) + "";

			// 获取子节点进行判断是否存在，不存在的话就进行生成，存在就不处理继续往下走
			HashMap<String, AcHashNode> children = p.children;

			if(!children.containsKey(s)) {
				// 子节点赋值
				AcHashNode acHashNode = new AcHashNode(s);
				children.put(s, acHashNode);
			}

			p = children.get(s);
		}

		// 非常重要这里，否则的话无法进行检索到敏感词的位置
		p.length = text.length();

		// 将叶子节点标识为true
		p.isEndingChar = true;
	}

	/**
	 * 构建失败指针
	 */
	public void buildFailurePointer() {
		// 使用广度遍历.
		Queue<AcHashNode> queue = new LinkedList<>();

		// 初始化头节点
		root.fail = null;
		queue.add(root);

		// 遍历树
		while(!queue.isEmpty()) {
			AcHashNode cur = queue.remove(); // 获取链表的头节点，为其寻找失败节点。

			for (String key : cur.children.keySet()) {
				AcHashNode children = cur.children.get(key);

				if(cur == root) { // 如果是root的子节点，则其失败指针指向 root
					children.fail = root;
				} else {  // 处理失败指针的位置
					AcHashNode q = cur.fail; // 判断父节点的失败指针
					while(null != q) {
						AcHashNode qc = q.children.get(key); // 获取父节点的子节点。

						if(null != qc) {
							children.fail = qc;
							break;
						}

						q = q.fail;
					}

					if(null == q) { // 不存在当前值的上级的节点。则指向 root
						children.fail = root;
					}
				}

				queue.add(children);
			}
		}
	}

	/**
	 * 匹配所有的字符串
	 * @param text
	 * @return
	 */
	public List<String> match(String text) {
		List<String> ans = new ArrayList<>();

		AcHashNode p = root;

		int n = text.length();
		for (int i = 0; i < n; i++) {
			String key = text.charAt(i)+"";

			while(p.children.get(key) == null && p != root) { // 如果当前子节点不存在该值，就找失败指针
				p = p.fail;
			}

			p = p.children.get(key);
			if(null == p) p = root; // 如果没有匹配的就重新从root匹配

			AcHashNode tmp = p;
			while (tmp != root) {
				if(tmp.isEndingChar) {
					int pos = i -tmp.length+1;

					ans.add(text.substring(pos, pos+ tmp.length));
				}
				tmp = tmp.fail;
			}
		}
		return ans;
	}

	/**
	 * 返回是否包含敏感词
	 * @param text
	 * @return
	 */
	public boolean contains(String text) {
		AcHashNode p = root;

		int n = text.length();
		for (int i = 0; i < n; i++) {
			String key = text.charAt(i)+"";

			while(p.children.get(key) == null && p != root) { // 如果当前子节点不存在该值，就找失败指针
				p = p.fail;
			}

			p = p.children.get(key);
			if(null == p) p = root; // 如果没有匹配的就重新从root匹配

			AcHashNode tmp = p;
			while (tmp != root) {
				if(tmp.isEndingChar) return true;
				tmp = tmp.fail;
			}
		}
		return false;
	}

	/**
	 * 替换敏感词
	 * @param text
	 * @param sub
	 * @return
	 */
	public String replace(String text, String sub) {
		List<String> match = match(text);
		for (String s : match) {
			text = text.replaceAll(s, sub);
		}

		return text;
	}

	/**
	 * 获取实例
	 * @return
	 */
	public AcHashTric newInstance() {
		return new AcHashTric();
	}

	/**
	 * 初始化字典树
	 */
	public void init(List<String> strs) {
		for (int i = 0; i < strs.size(); i++) {
			insert(strs.get(i));
		}
		buildFailurePointer();
	}

	

	public static void main(String[] args) {
		AcHashTric acTric = new AcHashTric();

		acTric.insert("hello");
		acTric.insert("heo");
		acTric.insert("ello");
		acTric.insert("ahello");

		acTric.buildFailurePointer();

		String replace = acTric.replace("helloasdfashelello", "**"); // **asdfashel**

		System.out.println(replace);
	}

}
